1124. 表现良好的最长时间段【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 前缀和 + 哈希表

1. 📝 题目描述

• leetcode

给你一份工作时间表 hours，上面记录着某一位员工每天的工作小时数。

我们认为当员工一天中的工作小时数大于 8 小时的时候，那么这一天就是「劳累的一天」。

所谓「表现良好的时间段」，意味在这段时间内，「劳累的天数」是严格 大于「不劳累的天数」。

请你返回「表现良好时间段」的最大长度。

---

示例 1：

输入：hours = [9,9,6,0,6,6,9]
输出：3
解释：最长的表现良好时间段是 [9,9,6]。

示例 2：

输入：hours = [6,6,6]
输出：0

---

提示：

• 1 <= hours.length <= 10^4
• 0 <= hours[i] <= 16

2. 🎯 s.1 - 前缀和 + 哈希表

js] <<< ./solutions/1/1.c [c] <<< ./solutions/1/1.py [py

/**
 * @param {number[]} hours
 * @return {number}
 */
var longestWPI = function (hours) {
  const map = new Map()
  let prefix = 0,
    res = 0
  for (let i = 0; i < hours.length; i++) {
    prefix += hours[i] > 8 ? 1 : -1
    if (prefix > 0) {
      res = i + 1
    } else {
      if (!map.has(prefix)) map.set(prefix, i)
      if (map.has(prefix - 1)) {
        res = Math.max(res, i - map.get(prefix - 1))
      }
    }
  }
  return res
}

• 时间复杂度：$O(n)$，其中 $n$ 是数组的长度
• 空间复杂度：$O(n)$，哈希表的开销

算法思路：

• 将工作 > 8 小时的天记为 +1，否则记为 -1，转化为前缀和问题
• 若前缀和 > 0，则从开头到当前位置都是良好时间段
• 否则查找 prefix-1 的最早出现位置，该位置到当前的子数组即为候选答案